package TREE;
import hij.linkqueue;
import hij.queue;
public class BinTree implements tree{
    private Node root;
    public int j=0;
    
    public BinTree(){
        this.root=null;
    }
    public void InitBiTree() {
        this.root=null;
    }

 
    public void destoryBiTree() {
        this.root=null;
    }

 
    public void ClearBiTree() {
        this.root=null;
    }

    
    public boolean BiTreeEmpty() {
       return null==this.root;
    }

  
    public int BiTreeDepth() {
         return  doBiTreeDepth(this.root);
    }

    public int doBiTreeDepth(Node o) {
       if(null==this.root)
           throw new IllegalArgumentException("树已经为空");
       if(null==o)
           return 0;
       int LeftNumber=doBiTreeDepth(o.left)+1;
       int RightNumber=doBiTreeDepth(o.right)+1;
       return LeftNumber>RightNumber?LeftNumber:RightNumber;
    }

    public Node Root() {
        if(null==this.root)
            throw new IllegalArgumentException("数已经为空");
        return this.root;
    }

    public Object Value(Node o) {
       if(null==this.root)
             throw new IllegalArgumentException("数已经为空");
       queue a=new linkqueue();
       a.enQueue(this.root);
       j=0;
       while(a.isEmpty()==false){
           Node pos=(Node)a.deQueue();
           if(pos==o){
              j=1;
              break;
           }
           if(pos.left!=null)
           {
           a.enQueue(pos.left);
           }
           if(pos.right!=null)
           {
           a.enQueue(pos.right);
           }
       }
       if(j==1)
         return o.data;
       else 
           throw new IllegalArgumentException("没有找到与"+o.data+"匹配的结点");
    }

    public void Assign(Node pos, Object o) {
      if(null==this.root)
             throw new IllegalArgumentException("数已经为空");
       Object m=this.Value(pos);
       if(j==1)
           pos.data=o;
       else 
           throw new IllegalArgumentException("没有找到与"+pos.data+"匹配的结点");
    }

    public Node Parent(Node o) {
       if(null==this.root)
           throw new IllegalArgumentException("树的根节点已经为空");
       Object a=this.Value(o);
       if(null==o.parent)
           throw new IllegalArgumentException("父类为空");
       return o.parent;
    }

    public Node LeftChild(Node o) {
        if(null==this.root)
           throw new IllegalArgumentException("树的根节点已经为空");
        Object a=this.Value(o);
        if(o==null)
            throw new IllegalArgumentException("结点为空，没有子类");
        if(null==o.left)
            throw new IllegalArgumentException("结点"+o.data+"的左孩子为空");
        return o.left;
    }

    public Node RightChild(Node o) {
        if(null==this.root)
           throw new IllegalArgumentException("树的根节点已经为空");
        Object a=this.Value(o);
        if(o==null)
            throw new IllegalArgumentException("结点为空，没有子类");
        if(null==o.right)
            throw new IllegalArgumentException("结点"+o.data+"的右孩子为空");
        return o.right;
    }

    public Node LeftSibling(Node o) {
        if(null==this.root)
           throw new IllegalArgumentException("树的根节点已经为空");
        Object a=this.Value(o);
        if(null==Parent(o).left||o==Parent(o).left||null==o.parent)
            throw new IllegalArgumentException("没有左兄弟");
        return this.Parent(o).left;
    }

    public Node RightSibling(Node o) {
        if(null==this.root)
           throw new IllegalArgumentException("树的根节点已经为空");
        Object a=this.Value(o);
        if(null==Parent(o).right||o==Parent(o).right||null==o.parent)
            throw new IllegalArgumentException("没有右兄弟");
        return this.Parent(o).right;
    }

    public void InOrderTraverse(Node o) {
       if(null!=o){
          InOrderTraverse(o.left);
          System.out.print(" "+o.data);
          InOrderTraverse(o.right);
        } 
    }

    public void PostOrderTraverse(Node o) {
        if(null!=o){
            PostOrderTraverse(o.left);
            PostOrderTraverse(o.right);
            System.out.print(" "+o.data);
        }
    }
    
    public void LevelTraverse(Node o){
       if(null==o)
           throw new IllegalArgumentException("数已经为空");
       queue a=new linkqueue();
       a.enQueue(o);
       while(a.isEmpty()==false){
           Node pos=(Node)a.deQueue();
           System.out.print(" "+pos.data);
           if(pos.left!=null)
           {
           a.enQueue(pos.left);
           }
           if(pos.right!=null)
           {
           a.enQueue(pos.right);
           }
       }
    }
    
    public void PreOrderTreverse(Node o) {
       if(null!=o){
            System.out.print(" "+o.data);
            PreOrderTreverse(o.left);
            PreOrderTreverse(o.right);
        }
    }
    
    public Node insert(Node a,int o,Node b){
       Node pos=new Node();
         if(0==o&&null==b){
        	 this.root=a;
        	 a.left=null;
        	 a.right=null;
        	 a.parent=null;
                 pos=a;
         }
         if(o==1){
        	 if(a.left==null){
        	 a.left=b;
        	 b.parent=a;
                 pos=b;}
        	 else throw new IllegalArgumentException("结点"+a.data+"已经有左子树");
         }
         if(o==-1){
        	 if(a.right==null){
        	 a.right=b;
        	 b.parent=a;
        	 pos=b;}
        	 else throw new IllegalArgumentException("结点"+a.data+"已经有右子树");
         }
         return pos;
    }
    
   public void delete(Node pos,int o){
       if(this.root==null)
           throw new IllegalArgumentException("树的根节点已经为空");
       Object a=this.Value(pos);
    	if(o==1){
                if(pos.left!=null){
    		   pos.left=null;
                }
                else
                   throw new IllegalArgumentException("结点"+pos.data+"没有左子树");
    	}
    	if(o==-1){
                if(pos.right!=null){
    		  pos.right=null;
                }
                else
                throw new IllegalArgumentException("结点"+pos.data+"没有右子树");
    	}
    	
    } 
}
